package com.xinpan.exercise;

import java.util.HashMap;
import java.util.Map;


public class InPreConstructTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(preorder.length == 0)
            return null;
        
        Map<Integer, Integer> posMap = new HashMap<Integer, Integer>();
        
        for(int i = 0; i < inorder.length; i++)
            posMap.put(inorder[i], i);
            
        int pos = 0;
        int val = preorder[pos];
        int div = posMap.get(val);
        
        TreeNode root = new TreeNode(val);
        root.left = findRoot(0, div-1, inorder, preorder, pos+1, posMap);
        root.right = findRoot(div+1, inorder.length-1, inorder, preorder, pos+1+(div-0), posMap);
        
        return root;
    }
    
    public TreeNode findRoot(int s, int e, int[] inorder, int[] preorder, int pos,
                                Map<Integer, Integer> posMap)
    {
        if(e < s)
            return null;
        else if(e == s)
            return new TreeNode(preorder[pos]);
        
        int val = preorder[pos];
        int div = posMap.get(val);
        
        TreeNode root = new TreeNode(val);
        root.left = findRoot(s, div-1, inorder, preorder, pos+1, posMap);
        root.right = findRoot(div+1, e, inorder, preorder, pos+1+(div-s), posMap);
        
        return root;
    }
    
    class TreeNode 
    {
      	 int val;
      	 TreeNode left;
      	 TreeNode right;
      	 TreeNode(int x) { val = x; }
    }
    
    public static void main(String[] args)
    {
    	InPreConstructTree ipct = new InPreConstructTree();
    	int[] in = {};
    	int[] pre = {};
    	ipct.buildTree(pre, in);
    }
    
}
